package com.zwj.interview.二分查找;

/**
 * 在一个排序的数组中，除一个数字只出现一次之外，其他数字都出现了两次，
 * 请找出这个唯一只出现一次的数字。例如，在数组[1，1，2，2，3，4，4，5，5]中，数字3只出现了一次
 * <p>
 * 如果将题目的条件稍稍改动，输入的数组没有经过排序，其他条件不变，那么这就是另一类很经典的面试题。
 * 由于两个相同的数字异或的结果是0，因此如果将数组中所有数字异或，最终的结果就是那个唯一只出现一次的数字
 */
public class 有序数组中只出现一次的数字 {

    /**
     * 数组中的数字每两个分成一组，最初的若干组的两个数字都是相同的。但遇到了只出现一次的数字之后，
     * 情况发生变化。这个只出现一次的数字和后面的数字结合成一组，导致后面所有出现两次的数字都被分到两个不同的组，
     * 即后面所有组的两个数字都不相同。(由此可见，只出现一次的数字正好是第1个两个数字不相等的分组的第1个数字)
     * <p>
     * 依旧基于二分法进行
     * <p>
     * 将数组中的数字每两个分为一组。先找出位于中间的一组，确定这一组的两个数字是否相同。
     * 如果两个数字相同，那么那个只出现一次的数字一定在它的后面，因此接着查找它的后半部分。
     * 如果两个数字不相同，那么接着检查这一组是不是第1组两个数字不相同的分组。如果是第1组，
     * 那么这一组的第1个数字就是只出现一次的数字。如果不是第1组，那么第1组一定在它的前面，因此接着查找它的前半部分
     *
     * 重点:
     * 将数组两两组队，找到第一个不相同的数对，那么这个数对的第一个数字就是要找的数字
     */

    public int singleNonDuplicate(int[] nums) {
        //left是第一个分组的编号
        int left = 0;
        //right是查找范围内最后一个分组的编号，也就是说所有元素分成了（nums.length / 2）个组
        int right = nums.length / 2;
        while (left <= right) {
            //中间分组的编号
            int mid = (left + right) / 2;
            //中间分组的第一个数字在数组中的下标
            int i = mid * 2;
            /**
             * 如果说中间的分组两个数字不一样的话，那么就需要看这个分组是不是第一个数字不相同的分组
             */
            if (i < nums.length - 1 && nums[i] != nums[i + 1]) {
                //如果说前一个分组的两个数字是一样的话，那么中间分组的第一个数字就是我们要找的了
                if (mid == 0 || nums[i - 2] == nums[i - 1]) {
                    return nums[i];
                }
                //如果走到这里，说明中间分组的前一组也不同，需要推进right
                right = mid - 1;
            } else {
                //如果中间分组的两个数字也相同的话，就需要推进left
                left = mid + 1;
            }
        }
        /**
         * 走到这里，说明那个唯一不同的元素就在数组最后一位
         */
        return nums[nums.length - 1];
    }

}
